#include <algorithm>
#include <cfloat>
#include <cmath>
#include <fstream>
#include <iostream>
#include <iterator>
#include <ext/hash_map>
#include <map>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include "u1.h"

/*
 * The simplest pagerank-based similarity measure I could think of:
 *   Find the movies in the given ranking list.
 *   Number them 1 .. K, where K is the number of movies.
 *   Set the similarity of movie i wrt movie j to 1 / (abs(i - j) + 1)
 * 
 * Takes no arguments. Takes a ....movies.ranked (see pagerank_movie_ids) file
 * on standard in. Outputs similarity matrix on standard out.
 */
using namespace __gnu_cxx;
using namespace std;

int main(int argc, char *argv[]) {

  /* Read netflix movie ids in rank order from standard in; pagerank_movie_ids
   * was written to output in this format. */
  hash_map<int,int> movie_id_ranks(NUM_MOVIES);
  int rank = 0;
  while (cin.good()) {
    int movie_id;
    double page_number;
    cin >> movie_id;
    cin >> page_number;
    if (cin.good()) {
      movie_id_ranks[movie_id] = rank;
      ++rank;
    }
  }
  TRACE << "Ranked " << movie_id_ranks.size() << " movies." << endl;

  /* Output similarity matrix. */
  int estimate_count = 0;
  for (unsigned int i = 1; i <= NUM_MOVIES; ++i) {
    for (unsigned int j = 1; j <= NUM_MOVIES; ++j) {
      int rank_i = -1, rank_j = -1;
      hash_map<int,int>::const_iterator it = movie_id_ranks.find(i);
      if (it != movie_id_ranks.end())
        rank_i = it->second;
      it = movie_id_ranks.find(j);
      if (it != movie_id_ranks.end())
        rank_j = it->second;
      if (rank_i < 0 || rank_j < 0) {
        // We don't know the similarity of these two movies.
        cout << "0 ";
      } else {
        double similarity = 1.0 / (abs(rank_j - rank_i) + 1);
        cout << similarity << " ";
        ++estimate_count;
      }
    }
    cout<<endl;
  }
  TRACE << "Done; made " << estimate_count << " estimates." << endl;

  return 0;
}

/*
* Copyright (c) 2009 John Lees-Miller
* 
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
* 
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/

